import java.util.*;

public class Test {

    //去重
    public static void func1(int[] array){
        Set<Integer> set = new HashSet<>();
        for (int i = 0 ; i < array.length; i++){
            set.add(array[i]);
        }
        System.out.println(set);
    }


    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0 ; i < nums.length; i++){
            //有删掉，没有放进来
            if (!set.contains(nums[i])){
                set.add(nums[i]);
            }else {
                set.remove(nums[i]);
            }
        }
        //走到这里来说，只有一个数据
        for (int i = 0 ; i < nums.length; i++){
            if (set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }


    //用异或来
    public int singleNumber2(int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++){
            ret ^= nums[i];
        }
        return ret;
    }


    /*public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null){
            Node node = new Node(cur.val);
            map.put(cur,node);
            //老节点和新节点放进去
            cur = cur.next;
        }

        //第一遍遍历wanc，此时遍历第二遍，修改next和random的值

        cur = head;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            //修改新节点的next
            map.get(cur).random = map.get(cur.random);
            //修改新节点的random
            cur = cur.next;
        }

        return map.get(head);
    }*/


    public int numJewelsInStones(String jewels, String stones) {
        int count = 0;
        Set<Character> set = new HashSet<>();

        for(char c : jewels.toCharArray()){
            set.add(c);
        }

        for(char c : stones.toCharArray()){
            if(set.contains(c)){
                count++;
            }
        }

        return count;
    }




    public static void main1(String[] args) {
        int[] array = {1,2,3,2,1};
        func1(array);
    }

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        //注意hasNext , hasNextLine的区别
        while (in.hasNextLine()){
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            func(str1,str2);
        }

        //func("7_This_is_a_test","_hs_s_a_es");

    }


    //str1应该输入的
    //str2实际输入的
    public static void func(String str1,String str2){
        Set<Character> set = new HashSet<>();
        //把实际输入的放进集合当中
        for (char ch : str2.toUpperCase().toCharArray()){
            //变成大写之后变成数组
            set.add(ch);
        }

        Set<Character> set2 = new HashSet<>();
        for (char ch : str1.toUpperCase().toCharArray()){
            //变成大写之后变成数组
            if (!set.contains(ch) && !set2.contains(ch)){
                set2.add(ch);//把坏的键盘放到单独的集合里
                System.out.print(ch);
            }
        }
    }



    //统计每个同学出现的次数
    //K-V
    //数字，几次
    public static void func2(int[] array){
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++){
            //以前没有
            if (map.get(array[i]) == null){
                map.put(array[i],1);
            }else {
                //以前有
                int val = map.get(array[i]);
                map.put(array[i],val+1);
            }
        }
        System.out.println(map);
    }

    public static void main3(String[] args) {
        int[] array = {1,2,3,2,1,2,1};
        func2(array);
    }


    public static List<String> toKFrequent(String[] words,int k){
        //1.每个数据出现的次数
        Map<String,Integer> map = new HashMap<>();
        for (String s:words){
            //统计每个单词的次数
            if (map.get(s) == null){
                map.put(s,1);
            }else {
                //以前有
                int val = map.get(s);
                map.put(s,val+1);
            }
        }
        //次数统计完毕

        //2.统计完毕，建立一个小根堆
        //匿名内部类，实现了这个接口，重写了方法
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue() .compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());//根据字母顺序，变成大根堆
                }
                return o1.getValue() .compareTo(o2.getValue());
            }
        });

        //3.接下来遍历Map
        for (Map.Entry<String,Integer> entry: map.entrySet()){
            //K-V
            if (minHeap.size() < k){
                minHeap.offer(entry);
            }else {
                //放满，开始和堆顶元素比较
                Map.Entry<String,Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) == 0){
                    //频率一样的情况下，判断key值，key小的入
                    if (top.getKey().compareTo(entry.getKey()) > 0){
                        //出top 入entry
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else{
                    if (top.getValue().compareTo(entry.getValue()) < 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }

        }

        //4.小根堆的里面的元素出出来，放到一个集合里面，然后逆置
        List<String> ret = new ArrayList<>();
        for (int i = 0;i < k; i ++){
            String s = minHeap.poll().getKey();
            ret.add(s);
        }
        Collections.reverse(ret);//集合的工具
        return ret;
    }


    public static void main(String[] args) {
        String[] strings = {"a","b","c","c"};
        List<String> ret = toKFrequent(strings,3);
        System.out.println(ret);

    }
}
